import java.util.*;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/20
 * \* Time: 20:48
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 前K个高频单词 {
    /**
     * 先用哈希表统计单词的出现频率，然后因为题目要求前 K 大。所以构建一个 大小为 K 的小根堆按照上述规则自定义排序的比较器。
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        //统计每个单词出现的次数
        Map<String,Integer> count=new HashMap<>();
        for(String word:words){
            count.put(word,count.getOrDefault(word,0)+1);
        }

        // 2.构建小根堆 这里需要自己构建比较规则 此处为 lambda 写法 Java 的优先队列默认实现就是小根堆
        PriorityQueue<String> minHeap=new PriorityQueue<>((s1, s2)->{
            //如果出现次数相同就按字典序比较
            if(count.get(s1).equals(count.get(s2))){
                return s2.compareTo(s1);
            }else {
                return count.get(s1) - count.get(s2);
            }
        });

        // 3.依次向堆加入元素
        for(String s: count.keySet()){
            minHeap.offer(s);
            // 当堆中元素个数大于 k 个的时候，需要弹出堆顶最小的元素。
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // 4.依次弹出堆中的 K 个元素，放入结果集合中。
        List<String > res=new ArrayList<>(k);
        while (minHeap.size()>0){
            res.add(minHeap.poll());
        }

        // 5.注意最后需要反转元素的顺序。
        Collections.reverse(res);
        return res;
    }
}